OK ... I finished one of these 0PPS-pictures, and went on to my next POV-project ...

I'm working on something like the clutter-macro, we've already seen here ...

At least, I want to place a lot objects (currently spheres) in the scene (currently
on a surface, so its 2D) without intersection ...

currently I use the simple, dumb, standard algorithm, that checks for every new
sphere, if theres another one already placed, which would intersect. If so, then
I calculate another position, until I find a free place ...

The thing is, that this algorithm works in O(n^2) which means it can get quite slow
in POV-SDL (of course, not only SDL). Currently for an instance of n=10,000  I have
a parse-time of ~40mins, and I want to go even higher for n.

So I wonder, if there are other, more advanced algorithms out there, which are
faster ...

I thought about doing something like putting the spheres in boxes and only test
for the spheres, that are in the current and the adjacent boxes. This would save
the time to test EVERY other sphere, but would add some overhead for small number
of objects ...

So, has anyone done something like that already, or is there interest in such a
macro or at least testresults ?

If you are interested, I could do some tests when I have some time, but don't
count on this beeing soon ...

-- Jan

Post a reply to this message